// Copyright 2011, Vanya Davidenko.
// Кодировка файла: UTF-8. 
package info.iu9.red;



class DfaInterpreter {
  private final class CommandStateVisitor extends AbstractCommandStateVisitor {
    CommandStateVisitor() {
      unvisited_ = newStateIdsSetList();
      processed_ = newStateIdsSetList();
    }

    void visitStates(final boolean ignore_priority) {
      reset();
      while ( !unvisited_.isEmpty() ) {
        current_state_id_ = unvisited_.pop();
        state(current_state_id_).accept(this);

        if ( !ignore_priority && matched_ ) {
          break;
        }
      }
    }

    @Override
    protected boolean matched() {
      return matched_;
    }

    boolean canBeCached() {
      return can_be_cached_;
    }


    @Override
    public void visit(final MatchState s) {
      matched_ = true;
    }
    @Override
    public void visit(final BeginSaveState s) {
      inc();
    }
    @Override
    public void visit(final EndSaveState s) {
      inc();
    }

    @Override
    public void visit(final BeginningAnchorState s) {
      can_be_cached_ = false;
      super.visit(s);
    }
    @Override
    public void visit(final EndOfStringAnchorState s) {
      can_be_cached_ = false;
      super.visit(s);
    }
    @Override
    public void visit(final EndingAnchorState s) {
      can_be_cached_ = false;
      super.visit(s);
    }
    @Override
    public void visit(final ReverseEndingAnchorState s) {
      can_be_cached_ = false;
      super.visit(s);
    }
    @Override
    public void visit(final StringBeginningAnchorState s) {
      can_be_cached_ = false;
      super.visit(s);
    }
    @Override
    public void visit(final StringEndingAnchorState s) {
      can_be_cached_ = false;
      super.visit(s);
    }
    @Override
    public void visit(final MultiLineBeginningAnchorState s) {
      can_be_cached_ = false;
      super.visit(s);
    }
    @Override
    public void visit(final MultiLineEndingAnchorState s) {
      can_be_cached_ = false;
      super.visit(s);
    }
    @Override
    public void visit(final WordBoundaryAnchorState s) {
      can_be_cached_ = false;
      super.visit(s);
    }
    @Override
    public void visit(final InvertedWordBoundaryAnchorState s) {
      can_be_cached_ = false;
      super.visit(s);
    }

    @Override
    protected void addToResult() {
      // Вообще-то нужно добавлять не в голову, а хвост threads_, так как
      // первое состояние должно быть самым приоритетным.
      // Однако StateIdSetList — быстрая реализация множества + стека,
      // а сделав из него множество + дек мы повлияем на производительность.
      // При этом RegularStateVisitor совершает такую же ошибку,
      // добавляя элементы всегда в голову, поэтому после одной итерации
      // двух посетителей (CommandStateVisitor + RegularStateVisitor)
      // порядок элементов в threads_ восстанавливается.
      // Фактически получается очередь на двух стеках.
      threads_.push(current_state_id_);
    }
    @Override
    protected void newThread(final int new_state_id_offset) {
      move(new_state_id_offset);
    }
    @Override
    protected void move(final int next_state_id_offset) {
      final int next_state_id = current_state_id_ + next_state_id_offset;
      if ( processed_.push(next_state_id) ) {
        unvisited_.pushNew(next_state_id);
      }
    }

    private void reset() {
      setStringIterator(str_it_);
      can_be_cached_ = true;
      matched_ = false;
      unvisited_.swap(threads_);  // прям как в C++ :-)
      threads_.clear();

      // processed_ — экземпляр StateIdSetList, хотя хватило бы и BitSet.
      // Но в таком случае нужно каджый раз его очищать и иницилизировать.
      // При этом метод clear() работает, за O(n), а так — O(1).
      // Копирование вместо побитового пословное.
      unvisited_.copyTo(processed_);
    }

    private boolean can_be_cached_;
    private boolean matched_;
    private int current_state_id_;
    private final StateIdSetList unvisited_;
    private StateIdSetList processed_;
  }

////////////////////////////////////////////////////////////////////////////////

  private final class RegularStateVisitor extends AbstractRegularStateVisitor {
    RegularStateVisitor() {
      result_ = newStateIdsSetList();
    }

    void visitStates() {
      reset();
      while ( !threads_.isEmpty() ) {
        current_state_id_ = threads_.pop();
        state(current_state_id_).accept(this);
      }
      threads_.swap(result_);
    }

    @Override
    protected void incIf(final boolean condition) {
      if ( condition ) {
        result_.pushNew(current_state_id_ + 1);
      }
    }

    private void reset() {
      result_.clear();
      setStringIterator(str_it_);
    }

    private int current_state_id_;
    private final StateIdSetList result_;
  }

////////////////////////////////////////////////////////////////////////////////

  DfaInterpreter(final FiniteAutomata fa,
                 final int[] fact_map, final int num_of_fact) {
    // Добавляем к началу автомата .*? (ленивый пропуск всего, включая \n).
    // Тогда поиск подстроки — поиск первого MatchState,
    // а при проверке удовлетворения строки заданному шаблону fa
    // интерпретация начинается не с нулевого состояния,а сразу за добавленными.
    forward_fa_ = new FiniteAutomata();
    forward_fa_.append(anythingLazyFiniteAutomata());
    forward_fa_.append(fa);

    reverse_fa_ = fa.reversed();
    assert forward_fa_.size() > reverse_fa_.size();

    fa_ = forward_fa_;  // инциализация fa_ нужна для инициализации посетителей

    threads_ = newStateIdsSetList();

    cmd_v_ = new CommandStateVisitor();
    reg_v_ = new RegularStateVisitor();

    states_cache_ = new DfaStatesCache();
    fact_map_ = fact_map;
    num_of_fact_ = num_of_fact;
  }


  // Сопоставление строки string с шаблоном.
  // Начало и конец совпадают с границами строки.
  boolean matches(final String string) {
    reset(new ForwardStringIterator(string), forward_fa_, match_from_start_);
    return searchImpl(true, false, false) != -2;
  }

  // Поиск подстроки, соответствующей шаблону, в строке string.
  // Начало может быть в любой позиции (пропускаются символы до тех пор, пока
  // не начнется совпадение), конец — достижение первого MatchState.
  boolean contains(final String string) {
    reset(new ForwardStringIterator(string), forward_fa_, match_from_anywhere_);
    return searchImpl(false, true, false) != -2;
  }

  Submatch search(final String string) {
    final Submatch result = new Submatch(string);

    // Конец подстроки ищем как обычно, до тех пор, пока не найдем наиболее
    // приоритетный MatchState.
    reset(new ForwardStringIterator(string), forward_fa_, match_from_anywhere_);
    final int end = searchImpl(false, false, false);
    if ( end < 0 ) {
      return end == -2 ? null : result;
    }
    result.set_last(end);

    // Начало подстроки ищем в срезе string[0, last], итерируя в обратном
    // направлении по строке перевернутым автоматом без учета приоритета(!).
    // Если конец нашелся (то есть last >= 0), тогда начало точно будет найдено.
    reset(new ReverseStringIterator(string, end, -1), reverse_fa_, 0);
    result.set_first(searchImpl(false, false, true));

    return result;
  }


  // Поиск подстроки, соответствующей шаблону.
  // @param[in] full_match совпадение должно быть полным (true),
  //                       до любого символа (false).
  //             Пример: в строке "aaa" выражение "a+" при true найдет "aaa",
  //                     при false — "a" (в случае "a*" вообще пустую строку)
  //
  // @param[in] till_first_match совпадение должно быть максимально
  //            длинным (true) или прерываться при достижении первого совпадения
  //            (ленивый режим)
  //
  // @param[in] ignore_priority игнорировать приоритет.
  //            В случае прямого поиска, должен быть false, что позволит найти
  //            конец самого левого совпадения. В случае обратного поиска
  //            должен быть true, что позволит найти самое дальнее от конца
  //            (самое левое) начало.
  //            В случае false выражение (abc | b) в строке "abc" найдет "abc",
  //            а в случае true — только "b".
  //            Даннный режим нужен для осуществления поиска в обратную сторону:
  //            В строке "abc" при возврате по выражению (abc|bc) важно
  //            игнорировать порядок, чтобы найти самое левое вхождение.
  //
  // @retval -2 строка не найдена
  // @retval -1 текущий паттерн — пустая строка, он всегда найден
  // @retval >= 0 индекс конца подстроки (включительно).
  private int searchImpl(final boolean full_match,
                         final boolean till_first_match,
                         final boolean ignore_priority) {
    // Кэш быстро перестроится, зато не нужно заносить тип автомата
    // (прямой, обратный) и флаги в DfaCachedState, что привело бы к разбуханию.
    states_cache_.clear();

    int result = -2;

    final StateIdSetList threads_object = threads_;
    DfaCachedState prev_cached_state = null;
    DfaCachedState cached_state = null;

    for ( int c = str_it_.next() ; c != str_it_.EOL ; c = str_it_.next() ) {
      boolean matched = false;
      boolean is_empty = false;
      final int fact_c = fact_map_[c];
      assert fact_c < num_of_fact_;

      if ( prev_cached_state != null &&
          ( cached_state = prev_cached_state.next(fact_c) ) != null ) {
        matched = cached_state.matched();
        is_empty = cached_state.isEmpty();
        threads_ = null;

      } else {
        final int[] dense;
        final int size;
        if ( threads_ != null ) {
          assert threads_ == threads_object;
          dense = threads_.dense();
          size = threads_.size();
        } else {
          assert prev_cached_state != null;
          dense = prev_cached_state.dense();
          size = prev_cached_state.size();
        }

        if ( (cached_state = states_cache_.get(dense, size, fact_c)) != null ) {
          matched = cached_state.matched();
          is_empty = cached_state.isEmpty();
          threads_ = null;

        } else {
          final DfaCacheKey cache_key = DfaCacheKey.make(dense, size, fact_c);

          if ( threads_ == null ) {
            prev_cached_state.restoreTo(threads_object);
            threads_ = threads_object;
          }
          cmd_v_.visitStates(ignore_priority);
          reg_v_.visitStates();
          matched = cmd_v_.matched();
          is_empty = threads_.isEmpty();

          if ( till_first_match && matched ) {
            return str_it_.prevIndex();
          }

          if ( cmd_v_.canBeCached() ) {
            cached_state = DfaCachedState.make(threads_,matched, num_of_fact_);
            states_cache_.put(cache_key, cached_state);
          }
        }

        if ( prev_cached_state != null && cached_state != null ) {
          prev_cached_state.set_next(cached_state, fact_c);
        }
      }

      if ( !full_match && matched ) {
        result = str_it_.prevIndex();
      }

      if ( is_empty ) {  // должно идти после предыдущей проверки!
        break;
      }

      prev_cached_state = cached_state;
      cached_state = null;
    }

    if ( threads_ == null ) {
      prev_cached_state.restoreTo(threads_object);
      threads_ = threads_object;
    }
    cmd_v_.visitStates(ignore_priority);
    if ( cmd_v_.matched() ) {
      return str_it_.prevIndex();
    } else if ( full_match ) {
      return -2;
    } else {
      return result;
    }
  }

  private void reset(final StringIterator str_it,
                     final FiniteAutomata fa, final int first_state) {
    fa_ = fa;
    threads_.clear();
    threads_.push(first_state);
    str_it_ = str_it;
  }


  private State state(final int state_id) {
    return fa_.get(state_id);
  }
  private StateIdSetList newStateIdsSetList() {
    return new StateIdSetList(fa_.size());
  }

  // .*?
  private static FiniteAutomata anythingLazyFiniteAutomata() {
    final FiniteAutomata fa = new FiniteAutomata();
    fa.append(new DotAllState());
    fa.zeroOrMore(true);  // lazy
    return fa;
  }


  private static final int match_from_start_ = anythingLazyFiniteAutomata().size();
  private static final int match_from_anywhere_ = 0;

  private final FiniteAutomata forward_fa_;
  private final FiniteAutomata reverse_fa_;
  private FiniteAutomata fa_;

  private final CommandStateVisitor cmd_v_;
  private final RegularStateVisitor reg_v_;

  private final DfaStatesCache states_cache_;
  private final int[] fact_map_;
  private final int num_of_fact_;

  private StringIterator str_it_;
  private StateIdSetList threads_;
}


